//
//  ProblemOffer39.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/12.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 39. 数组中出现次数超过一半的数字 ✅
 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 示例 1:
     输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     输出: 2
 限制：
    1 <= 数组长度 <= 50000
 */
@objcMembers class ProblemOffer39: NSObject {
    func solution() {
        print(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]))
        print(majorityElementT([1, 2, 3, 2, 2, 2, 5, 4, 2]))
    }
    
    /*
     排序，中间数肯定是超过一半的数
     */
    func majorityElement(_ nums: [Int]) -> Int {
        let sNums = nums.sorted()
        return sNums[sNums.count/2]
    }
    
    /*
     投票法：
     假如：我们给众数变成=1，其他数变成=-1，那么数组的和一定 >0 , 因为众数个数 > 其他数字
     现在我们不知道众数是谁，我们可以假设第一个数字是众数，然后求和，知道和==0的情况，那么：
     第一个数字是普通数字时，如果遇到其他数字时，让和==0，那么后面众数的比例更多了
     第一个数字是普通数字时，如果遇到众数时，让和==0，那么后面众数的比例不变
     第一个数字是众数时，那么最后的和一定 > 0
     */
    func majorityElementT(_ nums: [Int]) -> Int {
        var score = 0   // 和
        var x = 0       // 假设众数的位置
        for n in nums {
            if score == 0 {
                x = n
            }
            
            score += (x == n ? 1 : -1)
        }
        
        return x
    }
}
